package dp;

public class MaxSubArray53 {
    int maxSubSum = Integer.MIN_VALUE;

    static int maxElement;

    public static int maxSubArray(int[] nums) {
        if (nums.length == 1)
            return nums[0];
        maxElement = nums[0];
        return maxSubArrayRecur(nums, 0, 0);
    }

    //brute force is down, optimization awaits
    public static int maxSubArrayRecur(int[] nums, int sum, int index) {
        if (index == nums.length) {
            return sum == 0 ? maxElement : sum;
        }
        maxElement = Math.max(maxElement, nums[index]);
        // add the element to sum and slide downwards
        int sum1 = maxSubArrayRecur(nums, sum + nums[index], index + 1);
        // slide down the window and ignore current element
        int sum2 = maxSubArrayRecur(nums, 0, index + 1);
        // skip all remaining elements
        int sum3 = sum == 0 ? maxElement : sum;
        return Math.max(Math.max(sum1, sum2), sum3);

    }

    public static int maxSubArrayGreedy(int nums[]) {
        int curMaxSum = nums[0], maxSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            curMaxSum = Math.max(curMaxSum + nums[i], nums[i]);
            maxSum = Math.max(curMaxSum, maxSum);
        }
        return maxSum;
    }

    public static void main(String[] args) {
        System.out.println(maxSubArrayGreedy(new int[]{-2, -3, 0,-1,4,2,-1}));
    }
}
